# 

# 

# Ford-Fulkerson算法是一种用于解决网络流问题的经典算法，其核心思想是通过不断地在残差图中寻找增广路径（augmenting paths）来增加流，直到找不到增广路径为止，此时所得到的流即为最大流。下面我将对Ford-Fulkerson算法进行详细解释，并提供一个Python代码示例。

# 

# ### 算法解释

# 

# Ford-Fulkerson算法基于以下几个关键概念：

# 

# 1. **剩余容量（Residual Capacity）**：对于网络中的每条边，剩余容量等于其容量减去当前流量。只有当剩余容量大于0时，该边才能作为增广路径的一部分。

# 2. **残差图（Residual Graph）**：在Ford-Fulkerson算法中，我们不断地在残差图中寻找增广路径。残差图是一个与原网络具有相同顶点和边的网络，但边的容量变为剩余容量。

# 3. **增广路径（Augmenting Path）**：在残差图中，从源点到汇点的一条路径，且该路径上所有边的剩余容量均大于0，称为增广路径。

# 

# 算法的基本步骤如下：

# 

# 1. 初始化网络中的流量为0。

# 2. 在残差图中寻找一条增广路径。

# 3. 如果找到增广路径，则更新网络中的流量，增加流量值等于增广路径上的最小剩余容量。

# 4. 如果没有找到增广路径，算法结束，此时求解得到的流量即为最大流。

# 

# ### Python代码示例

# 

# 下面是一个使用Python实现的Ford-Fulkerson算法示例：

# 

# 

from collections import defaultdict, deque



class Graph:

    def __init__(self, vertices):

        self.V = vertices  # 顶点数

        self.graph = defaultdict(list)  # 使用字典表示邻接表



    def add_edge(self, u, v, w):

        self.graph[u].append((v, w))  # 添加边 (u, v) 和容量 w

        self.graph[v].append((u, 0))  # 添加反向边 (v, u) 和容量 0，用于后续流量回溯



    def ford_fulkerson(self, source, sink):

        parent = [-1] * (self.V)  # 用于记录增广路径的父节点

        max_flow = 0  # 最大流量



        while True:

            # 寻找增广路径

            if not self.bfs(source, sink, parent):

                break  # 如果没有找到增广路径，则退出循环



            # 计算增广路径上的最小剩余容量

            path_flow = float('inf')

            s = sink

            while s != source:

                u, cap = self.graph[parent[s]][s]

                path_flow = min(path_flow, cap)

                s = parent[s]



            # 更新流量

            max_flow += path_flow

            v = sink

            while v != source:

                u, _ = self.graph[parent[v]][v]

                self.graph[parent[v]][v] = (u, self.graph[parent[v]][v][1] - path_flow)

                u, _ = self.graph[v][parent[v]]

                self.graph[v][parent[v]] = (u, self.graph[v][parent[v]][1] + path_flow)

                v = parent[v]



        return max_flow



    def bfs(self, source, sink, parent):

        visited = [False] * (self.V)

        queue = deque()

        queue.append(source)

        visited[source] = True



        while queue:

            u = queue.popleft()

            for v, cap in self.graph[u]:

                if visited[v] == False and cap > 0:

                    queue.append(v)

                    visited[v] = True

                    parent[v] = u



        return visited[sink]  # 如果汇点被访问过，则返回True，表示找到了增广路径



# 示例用法

g = Graph(4)

g.add_edge(0, 1, 3)

g.add_edge(0, 2, 2)

g.add_edge(1, 2, 2)

g.add_edge(1, 3, 2)

g.add_edge(2, 3, 3)



print("最大流为:", g.ford_fulkerson(0, 3))  # 输出: 最大流为: 







处理结果：







### 算法解释

Ford-Fulkerson算法基于以下几个关键概念：

1. **剩余容量（Residual Capacity）**：对于网络中的每条边，剩余容量等于其容量减去当前流量。只有当剩余容量大于0时，该边才能作为增广路径的一部分。

**残差图（Residual Graph）**：在Ford-Fulkerson算法中，我们不断地在残差图中寻找增广路径。残差图是一个与原网络具有相同顶点和边的网络，但边的容量变为剩余容量。

**增广路径（Augmenting Path）**：在残差图中，从源点到汇点的一条路径，且该路径上所有边的剩余容量均大于0，称为增广路径。

算法的基本步骤如下：

1. 初始化网络中的流量为0。

在残差图中寻找一条增广路径。

如果找到增广路径，则更新网络中的流量，增加流量值等于增广路径上的最小剩余容量。

如果没有找到增广路径，算法结束，此时求解得到的流量即为最大流。

### Python代码示例

下面是一个使用Python实现的Ford-Fulkerson算法示例：

class Graph:

def __init__(self, vertices):

self.V = vertices  # 顶点数

self.graph = defaultdict(list)  # 使用字典表示邻接表

def add_edge(self, u, v, w):

self.graph[u].append((v, w))  # 添加边 (u, v) 和容量 w

self.graph[v].append((u, 0))  # 添加反向边 (v, u) 和容量 0，用于后续流量回溯

def ford_fulkerson(self, source, sink):

parent = [-1] * (self.V)  # 用于记录增广路径的父节点

max_flow = 0  # 最大流量

while True:

# 寻找增广路径

if not self.bfs(source, sink, parent):

break  # 如果没有找到增广路径，则退出循环

# 计算增广路径上的最小剩余容量

path_flow = float('inf')

s = sink

while s != source:

u, cap = self.graph[parent[s]][s]

path_flow = min(path_flow, cap)

s = parent[s]

# 更新流量

max_flow += path_flow

v = sink

while v != source:

u, _ = self.graph[parent[v]][v]

self.graph[parent[v]][v] = (u, self.graph[parent[v]][v][1] - path_flow)

u, _ = self.graph[v][parent[v]]

self.graph[v][parent[v]] = (u, self.graph[v][parent[v]][1] + path_flow)

v = parent[v]

return max_flow

def bfs(self, source, sink, parent):

visited = [False] * (self.V)

queue = deque()

queue.append(source)

visited[source] = True

while queue:

u = queue.popleft()

for v, cap in self.graph[u]:

if visited[v] == False and cap > 0:

queue.append(v)

visited[v] = True

parent[v] = u

return visited[sink]  # 如果汇点被访问过，则返回True，表示找到了增广路径

# 示例用法

print("最大流为:", g.ford_fulkerson(0, 3))  # 输出: 最大流为: 